package com.yhq.basic.algorithm;

/**
 * 斐波那契数列
 * 1，1，2，3，5，8，13，21 ...
 * 求第N项
 *
 * @author hqyin
 * @date 2023/7/5 11:57 上午
 */
public class FibonacciTest {

    public static void main(String[] args) {
//        System.out.println( fb1(0));
//        System.out.println( fb1(1));
//        System.out.println( fb1(2));
//        System.out.println( fb1(3));
//        System.out.println( fb1(4));


        System.out.println(fb2(0));
        System.out.println(fb2(1));
        System.out.println(fb2(2));
        System.out.println(fb2(3));
        System.out.println(fb2(4));
    }

    private static int fb2(int n) {
        if (n <= 1) {
            return 1;
        }

        int first = 1;
        int second = 1;
        int result = 0;
        for (int i = 2; i <= n; i++) {
            result = first + second;
            first = second;
            second = result;
        }
        return result;
    }

    private static int fb1(int n) {
        if (n <= 1) {
            return 1;
        }
        return fb1(n - 1) + fb1(n - 2);
    }
}
